package q70_climbStairs;

public class Solution_3 {
    public static void main(String[] args) {
        Solution_3 s = new Solution_3();
        System.out.println(s.climbStairs(45));
    }

    public int climbStairs(int n) {
        /**
         * 从上面的推断过程，查询即可知道，这就是斐波那契数列
         * 用数学公式也就是其通项可解
         */
        double sqrt_5 = Math.sqrt(5);
        double fib_n = Math.pow((1 + sqrt_5) / 2, n + 1) - Math.pow((1 - sqrt_5) / 2,n + 1);
        return (int)(fib_n / sqrt_5);

    }


}
